Search Results

Documents authored by Patt-Shamir, Boaz

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2022.13
Competitive Vertex Recoloring

Authors: Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
Motivated by placement of jobs in physical machines, we introduce and analyze the problem of online recoloring, or online disengagement. In this problem, we are given a set of n weighted vertices and a k-coloring of the vertices (vertices represent jobs, and colors represent physical machines). Edges, representing conflicts between jobs, are inserted in an online fashion. After every edge insertion, the algorithm must output a proper k-coloring of the vertices. The cost of a recoloring is the sum of weights of vertices whose color changed. Our aim is to minimize the competitive ratio of the algorithm, i.e., the ratio between the cost paid by the online algorithm and the cost paid by an optimal, offline algorithm. We consider a couple of polynomially-solvable coloring variants. Specifically, for 2-coloring bipartite graphs we present an O(log n)-competitive deterministic algorithm and an Ω(log n) lower bound on the competitive ratio of randomized algorithms. For (Δ+1)-coloring, we present tight bounds of Θ(Δ) and Θ(logΔ) on the competitive ratios of deterministic and randomized algorithms, respectively (where Δ denotes the maximum degree). We also consider a dynamic case which allows edge deletions as well as insertions. All our algorithms are applicable to the case where vertices are weighted and the cost of recoloring a vertex is its weight. All our lower bounds hold even in the unweighted case.
Cite as

Yossi Azar, Chay Machluf, Boaz Patt-Shamir, and Noam Touitou. Competitive Vertex Recoloring. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 13:1-13:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{azar_et_al:LIPIcs.ICALP.2022.13,
  author =	{Azar, Yossi and Machluf, Chay and Patt-Shamir, Boaz and Touitou, Noam},
  title =	{{Competitive Vertex Recoloring}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{13:1--13:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.13},
  URN =		{urn:nbn:de:0030-drops-163542},
  doi =		{10.4230/LIPIcs.ICALP.2022.13},
  annote =	{Keywords: coloring with recourse, anti-affinity constraints}
}
Document
DOI: 10.4230/LIPIcs.ICALP.2018.50
On the Probe Complexity of Local Computation Algorithms

Authors: Uriel Feige, Boaz Patt-Shamir, and Shai Vardi

Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Abstract
In the Local Computation Algorithms (LCA) model, the algorithm is asked to compute a part of the output by reading as little as possible from the input. For example, an LCA for coloring a graph is given a vertex name (as a "query"), and it should output the color assigned to that vertex after inquiring about some part of the graph topology using "probes"; all outputs must be consistent with the same coloring. LCAs are useful when the input is huge, and the output as a whole is not needed simultaneously. Most previous work on LCAs was limited to bounded-degree graphs, which seems inevitable because probes are of the form "what vertex is at the other end of edge i of vertex v?". In this work we study LCAs for unbounded-degree graphs. In particular, such LCAs are expected to probe the graph a number of times that is significantly smaller than the maximum, average, or even minimum degree. We show that there are problems that have very efficient LCAs on any graph - specifically, we show that there is an LCA for the weak coloring problem (where a coloring is legal if every vertex has a neighbor with a different color) that uses log^* n+O(1) probes to reply to any query. As another way of dealing with large degrees, we propose a more powerful type of probe which we call a strong probe: given a vertex name, it returns a list of its neighbors. Lower bounds for strong probes are stronger than ones in the edge probe model (which we call weak probes). Our main result in this model is that roughly Omega(sqrt{n}) strong probes are required to compute a maximal matching. Our findings include interesting separations between closely related problems. For weak probes, we show that while weak 3-coloring can be done with probe complexity log^* n+O(1), weak 2-coloring has probe complexity Omega(log n/log log n). For strong probes, our negative result for maximal matching is complemented by an LCA for (1-epsilon)-approximate maximum matching on regular graphs that uses O(1) strong probes, for any constant epsilon>0.
Cite as

Uriel Feige, Boaz Patt-Shamir, and Shai Vardi. On the Probe Complexity of Local Computation Algorithms. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 50:1-50:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{feige_et_al:LIPIcs.ICALP.2018.50,
  author =	{Feige, Uriel and Patt-Shamir, Boaz and Vardi, Shai},
  title =	{{On the Probe Complexity of Local Computation Algorithms}},
  booktitle =	{45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
  pages =	{50:1--50:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-076-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{107},
  editor =	{Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.50},
  URN =		{urn:nbn:de:0030-drops-90543},
  doi =		{10.4230/LIPIcs.ICALP.2018.50},
  annote =	{Keywords: Local computation algorithms, sublinear algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.472
Online Scheduling with Interval Conflicts

Authors: Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
In the problem of Scheduling with Interval Conflicts, there is a ground set of items indexed by integers, and the input is a collection of conflicts, each containing all the items whose index lies within some interval on the real line. Conflicts arrive in an online fashion. A scheduling algorithm must select, from each conflict, at most one survivor item, and the goal is to maximize the number (or weight) of items that survive all the conflicts they are involved in. We present a centralized deterministic online algorithm whose competitive ratio is O(log sigma), where sigma is the size of the largest conflict. For the distributed setting, we present another deterministic algorithm whose competitive ratio is 2 log sigma, in the special contiguous case, in which the item indices constitute a contiguous interval of integers. Our upper bounds are complemented by two lower bounds: one that shows that even in the contiguous case, all deterministic algorithms (centralized or distributed) have competitive ratio Omega(log sigma), and that in the non-contiguous case, no deterministic oblivious algorithm (i.e., a distributed algorithm that does not use communication) can have a bounded competitive ratio.
Cite as

Magnus M. Halldorsson, Boaz Patt-Shamir, and Dror Rawitz. Online Scheduling with Interval Conflicts. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 472-483, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{halldorsson_et_al:LIPIcs.STACS.2011.472,
  author =	{Halldorsson, Magnus M. and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Online Scheduling with Interval Conflicts}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{472--483},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.472},
  URN =		{urn:nbn:de:0030-drops-30363},
  doi =		{10.4230/LIPIcs.STACS.2011.472},
  annote =	{Keywords: online scheduling, online set packing, interval conflicts, competitive analysis, compound tasks, distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.STACS.2008.1331
Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental

Authors: Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz

Published in: LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Abstract
In the Multislope Ski Rental problem, the user needs a certain resource for some unknown period of time. To use the resource, the user must subscribe to one of several options, each of which consists of a one-time setup cost (``buying price''), and cost proportional to the duration of the usage (``rental rate''). The larger the price, the smaller the rent. The actual usage time is determined by an adversary, and the goal of an algorithm is to minimize the cost by choosing the best option at any point in time. Multislope Ski Rental is a natural generalization of the classical Ski Rental problem (where the only options are pure rent and pure buy), which is one of the fundamental problems of online computation. The Multislope Ski Rental problem is an abstraction of many problems where online decisions cannot be modeled by just two options, e.g., power management in systems which can be shut down in parts. In this paper we study randomized algorithms for Multislope Ski Rental. Our results include the best possible online randomized strategy for any additive instance, where the cost of switching from one option to another is the difference in their buying prices; and an algorithm that produces an $e$-competitive randomized strategy for any (non-additive) instance.
Cite as

Zvi Lotker, Boaz Patt-Shamir, and Dror Rawitz. Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 503-514, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{lotker_et_al:LIPIcs.STACS.2008.1331,
  author =	{Lotker, Zvi and Patt-Shamir, Boaz and Rawitz, Dror},
  title =	{{Rent, Lease or Buy: Randomized Algorithms for Multislope Ski Rental}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{503--514},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Albers, Susanne and Weil, Pascal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1331},
  URN =		{urn:nbn:de:0030-drops-13313},
  doi =		{10.4230/LIPIcs.STACS.2008.1331},
  annote =	{Keywords: Competitive analysis, ski rental, randomized algorithms}
}
Document
DOI: 10.4230/DagSemProc.07411.5
High Entropy Random Selection Protocols

Authors: Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
We study the two party problem of randomly selecting a string among all the strings of length n. We want the protocol to have the property that the output distribution has high entropy, even when one of the two parties is dishonest and deviates from the protocol. We develop protocols that achieve high, close to n, entropy. In the literature the randomness guarantee is usually expressed as being close to the uniform distribution or in terms of resiliency. The notion of entropy is not directly comparable to that of resiliency, but we establish a connection between the two that allows us to compare our protocols with the existing ones. We construct an explicit protocol that yields entropy n - O(1) and has 4log^* n rounds, improving over the protocol of Goldwasser et al. that also achieves this entropy but needs O(n) rounds. Both these protocols need O(n^2) bits of communication. Next we reduce the communication in our protocols. We show the existence, non-explicitly, of a protocol that has 6-rounds, 2n + 8log n bits of communication and yields entropy n- O(log n) and min-entropy n/2 - O(log n). Our protocol achieves the same entropy bound as the recent, also non-explicit, protocol of Gradwohl et al., however achieves much higher min-entropy: n/2 - O(log n) versus O(log n). Finally we exhibit very simple explicit protocols. We connect the security parameter of these geometric protocols with the well studied Kakeya problem motivated by harmonic analysis and analytical number theory. We are only able to prove that these protocols have entropy 3n/4 but still n/2 - O(log n) min-entropy. Therefore they do not perform as well with respect to the explicit constructions of Gradwohl et al. entropy-wise, but still have much better min-entropy. We conjecture that these simple protocols achieve n -o(n) entropy. Our geometric construction and its relation to the Kakeya problem follows a new and different approach to the random selection problem than any of the previously known protocols.
Cite as

Nikolai K. Vereshchagin, Harry Buhrman, Matthias Cristandl, Michal Koucky, Zvi Lotker, and Boaz Patt-Shamir. High Entropy Random Selection Protocols. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{vereshchagin_et_al:DagSemProc.07411.5,
  author =	{Vereshchagin, Nikolai K. and Buhrman, Harry and Cristandl, Matthias and Koucky, Michal and Lotker, Zvi and Patt-Shamir, Boaz},
  title =	{{High Entropy Random Selection Protocols}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.5},
  URN =		{urn:nbn:de:0030-drops-13091},
  doi =		{10.4230/DagSemProc.07411.5},
  annote =	{Keywords: Shannon entropy, Random string ds}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact